%\newcommand{\CG}{{\cal G}}
\newcommand{\CG}{G}
\newcommand{\CN}{{\cal N}}
\newcommand{\attack}{$G_{\vec{a}}$}
\newcommand{\attackzero}{$G_{\vec{a}[v/0]}$}

\section{Model and Definitions}
\label{sec:game.model}
In this section, we present our game-theoretic model for network
security.  

\smallskip
\BfPara{Contact Graph} Let $V$ denote the set of users/devices
(henceforth, referred to as \emph{nodes}), each of which is assumed to
be an autonomous player.  Let $\CG$ denote the underlying contact
graph over the node set $V$; an edge $(u,v)\in \CG$ indicates that
nodes $u$ and $v$ are directly connected, so that if node $u$ is
infected by a worm it can potentially spread to node $v$.  
Let $N(v)$ denote the set of neighbors of $v$ in $\CG$.  We will
frequently work with certain subgraphs of $\CG$, for which we
introduce the following notation.  For any undirected graph $H$ and
subset $S$ of vertices of $H$, we let $H[S]$ denote the subgraph of
$H$ induced by the vertices in $S$.  \junk{For any undirected graph $H$,
vertex $u$ of $H$, and integer $k$, we let $N_k(H,u)$ denote the set
of vertices in $H$ that have a path from $u$ of length at most $k$.
}

\junk{
\BfPara{Connection Network and Contact Graph} Let $V$ denote the set
of users/devices (henceforth, referred to as \emph{nodes}), each of
which is assumed to be an autonomous player.  Let $\CN$ denote the
underlying connection network over the node set $V$; an edge $(u,v)\in
G$ indicates that nodes $u$ and $v$ are directly connected, so that if
node $u$ is infected by a worm it can potentially spread to node $v$.
The actual spread of a network infection depends not only on the
connection network and the initial infection location, but also on the
underlying communication profile of the nodes: who communicates with
whom.  We model this by a graph $\CG$ where an edge $(u,v) \in \CG$
indicates that $u$ communicates with $v$.  Thus, in the absence of any
virus protection, an infection initiated at node $u$ spreads to node
$v$ if and only if $(u,v)$ is in $\CG$, and $u$ and $v$ are connected
in $\CN$.
}

\junk{
In general, the connection network and the contact graph can be
independent of each other.  In practice, however, they are likely to
be highly correlated.  One particular correlation of practical
relevance is locality.  In this paper, we focus on the important case
where the contact graph is $d$th power of the connection network, for
a given parameter $d$: $\CG = \CN^d$.  That is, there is an edge $(u,v)$
in the contact graph if and only if $u$ and $v$ are at most $d$ hops
apart in the connection network.
}

\junk{That is, the set of nodes that can infect $v$ are precisely those that
are within distance $d$ in the contact graph, for a given parameter
$d$.  Within this parameterized class, we consider three separate
cases: $d = 1$, $d = Diam(G)$, and $2 \le d < Diam(G)$.  Let $deg(v) =
|N_1(v)|-1$ denote the degree of node $v$ in $G$.
}

\smallskip
\BfPara{Strategies} The strategy for each node $v$ is the decision of
whether to install an anti-virus software or not; we use a variable
$a_v\in[0,1]$ to denote the probability of securing the device.  In
this paper, we focus on \emph{pure} strategies, i.e., $a_v\in
\{0,1\}$. Let $\vec{a}$ denote the strategy vector of all
nodes. Following \cite{AspnesCY2006}, the \emph{attack graph}, \attack, is the subgraph of the contact graph induced by the set of insecure nodes according to $\vec{a}$.
For notational convenience, let $\vec{a}[v/x]$
be the strategy vector obtained by replacing $a_v$ by $x$ in the
vector $\vec{a}$. 

\junk{we define an \emph{attack
  graph}, $\CN_{\vec{a}}=\CN[V'=\{i:a_i=0\}]$ as the subgraph of the
connection network induced by the set of insecure nodes.  
}

\smallskip
\BfPara{Infection model} We assume that the infection is initiated at
a node chosen from $V$ according to an arbitrary probability
distribution.  Let $w_v$ denote the probability that node $v$ is
chosen as the initial infection point; for convenience, we introduce
the notation $w(S)$ to denote the sum of $w_v$ over all $v$ in $S$.
We parameterize the infection model by $d$, the maximum number of hops
over which the probability of infection spread is taken into account
in the decision making.  Thus, for a given contact
graph $\CG$ and strategy vector $\vec{a}$, an infection originating at
node $v$ infects node $u$ if and only if $u$ is within $d$ hops of $v$ in \attack.
\junk{
the subgraph of $\CG$ induced by $j$ and the nodes that are insecure
according to $\vec{a}$.} \junk{Formally, an infection originating at $i$
infects $j$ if and only if $i \in N_d(\CG[\vec{a}[j/0]], j)$. } 
Since $\CG$ is fixed and $d$ is clear from the
context, denote by $S_v(\vec{a})$ the set of nodes that are within $d$ hops of $v$ in \attackzero.
For a given strategy vector $\vec{a}$, therefore, the probability that node $v$
gets attacked in this model (denoted by $p_v(\vec{a})$) is
$w(S_v(\vec{a}))$.  

\junk{we abbreviate $N_d(\CG[\vec{a}[j/0]], j)$ by $S_j(\vec{a})$
in the remainder of the paper.
}

\smallskip
\BfPara{Generalized Network Security Game $\GNS{d}$} We now present
our model for a generalized network security game $\GNS{d}$,
parameterized by the hop-limit $d$ in the infection model.  The game
$\GNS{d}$ is specified by a contact graph $\CG$, initial infection
probability distribution $w$, and two costs per network node.  Let
$C_v$ denote the security cost (installing an anti-virus software) of user
$v$; we assume the software is fool-proof so that secure nodes do not
get attacked.  Let $L_v$ denote the infection cost of user $v$ (recovering from a worm
attack in case an insecure node $v$ gets attacked).  
Then, the cost to node $v$ is defined as

\[\cost_v\left(\bar{a}\right) = a_vC_v + (1-a_v)L_v\cdot p_v\left(\bar{a}\right).\]

A pure Nash equilibrium (henceforth, pure NE) is a strategy vector
$\vec{a}$ such that no node $v$ has any incentive to switch his
strategy, if all other nodes' strategies are fixed.\junk{ Let $\vec{a}[i/x]$
be the strategy vector obtained by replacing $a_i$ by $x$ in the
vector $\vec{a}$ (following \cite{AspnesCY2006}).} $\vec{a}$ is a
Nash equilibrium if $\cost_v(\vec{a}[v/x])\geq \cost_v(\vec{a})$ for
$x\in\{0,1\}$. Therefore, a pure NE is a natural configuration to aim
for in a non-cooperative game. It is easy to verify that the following
characterization of a pure NE (shown in \cite{AspnesCY2006} for the
special case where $\CG$ is the complete graph) holds.

\begin{lemma}
\label{lemma:game.nechar}
For $v\in V$, let $t_v=C_v/L_v$. A strategy vector
$\vec{a}\in\{0,1\}^n$ is a pure NE if the following conditions hold:
(i) for all $v$ such that $a_v=0$, $w(S_v(\vec{a}))\leq t_v$, and (ii)
for all $v$ such that $a_v=1$, $w(S_v(\vec{a}[v/0]))>t_v$.
\end{lemma}

\smallskip
\noindent
\BfPara{Social cost} The total social cost of a strategy profile is
the sum of the individual costs, which is $\cost\left(\bar{a}\right) =
\sum_{v=1}^n \cost_v\left(\bar{a}\right)$.  A socially optimum strategy
is a vector $\vec{a}$ that minimizes this cost - this is not
necessarily (and is not usually) a pure NE. Therefore, the cost of a
pure NE relative to the social cost is an important measure; the
maximum such ratio (i.e., over all possible pure NE) is also known as
the \emph{price of anarchy}~\cite{koutsoupias99}.

\junk{
\smallskip
\noindent
\BfPara{Effect of the parameter $d$} Our results on the existence of
equilibria and the quality of the approximations we achieve with
respect to social cost vary with $d$.  Qualitatively, we consider 3
regimes: $d = 1$, the local infection model; $d = \infty$, the global
infection model; and fixed $d$, where $1 < d < \infty$, the
$d$-neighborhood infection model.
}

For convenience, Table~\ref{tab:game.notation} summarizes our notations.

\begin{table}[htpb]
\caption{\label{tab:game.notation} A list of notations.
}
\begin{center}
\begin{tabular}{|c|p{4in}|}
\hline
Notations & Explanation \\
\hline
$G$ & Contact graph. \\
$G[S]$ & Subgraph of $G$ induced by the vertices in $S$. \\
$C_v$ & Security cost for node $v$ \\
$L_v$ & Infection cost for node $v$ \\
$\vec{a}$ & Strategy vector of nodes. \\
\attack & Attack graph, i.e. the subgraph of the contact graph induced by the set of insecure nodes according to $\vec{a}$. \\
$\vec{a}[v/x]$ & Strategy vector obtained by replacing $a_v$ by $x$ in the vector $\vec{a}$. \\
$S_v(\vec{a})$ & Set of nodes that are within $d$ hops of $v$ in \attackzero. \\
$w_v$ & Probability that node $v$ is chosen as the initial infection point. \\
$w(S)$ & Sum of $w_v$ over all $v$ in $S$. \\
$\cost_v(\vec{a})$ & Cost to node $v$ given strategy vector $\vec{a}$. \\
$\GNS{d}$ & Generalized network security game parameterized by the disease hop limit $d$. \\
\hline
\end{tabular}
\end{center}
\end{table}


%%%%%%%%
%%%%%%%%

